package org.example.sword2offer.primary;


import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author: lynn
 * @Descript:
 * @date: 2021/5/7 19:56
 * @version: 1.0
 */
public class Q29_1_QuickSortK {

    public static void main(String[] args) {
        int[] arr = {4,5,1,6,2,7,3,8};
        int k=5;
        ArrayList<Integer> res=getLeastNumbers(arr,k);
        System.out.printf(""+res);
        /*quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));*/
    }


    private static void  quickSort(int[] input,int startIndex,int endIndex){
        if (startIndex>=endIndex){
            return;
        }
        int p=partition(input,startIndex,endIndex);quickSort(input,startIndex,p-1); //fixme p-1
        quickSort(input,p+1,endIndex);
    }
    //获取基准元素的位置
    private static int partition(int[] input,int startIndex,int endIndex){
        int pivot=input[startIndex];
        int l=startIndex;
        int r=endIndex;
        while (l<r){
            //fixme 先右边，在左边，否则会出错！
            while (l<r && input[r]>=pivot){
                r--;
            }
            while (l<r && input[l]<=pivot){ //前开后闭
                l++;
            }
            if (l<r){
                int p=input[l];input[l]=input[r];input[r]=p;
            }
        }
        input[startIndex]=input[l];input[l]=pivot;return l;
    }


    public static ArrayList<Integer> getLeastNumbers(int [] input, int k) {
        ArrayList<Integer> arrayList=new ArrayList<>();
        quickSort(input,0,input.length-1);
        for (int i = 0; i <((input.length-k)<0?input.length:k); i++) {
            arrayList.add(input[i]);
        }
        return arrayList;
    }

}
